package day_2022_9_to_12.Day;

import java.util.*;

/**
 * @author haomin
 * @date 2022/11/16 22:04
 **/
public class Day72_Review {
    class Solution {
        public int[] spiralOrder(int[][] matrix) {
            if(matrix.length == 0 || matrix[0].length == 0) return new int[0];
            List<Integer> list = new LinkedList<>();
            int u = 0, l = 0, d = matrix.length-1, r = matrix[0].length-1;
            while(true){
                for(int i = l; i <= r; ++i) {
                    list.add(matrix[u][i]);
                }
                if(++u > d) break;
                for(int i = u; i <= d; ++i) {
                    list.add(matrix[i][r]);
                }
                if(--r < l) break;
                for(int i = r; i >= l; --i) {
                    list.add(matrix[d][i]);
                }
                if(--d < u) break;
                for(int i = d; i >= u; --i) {
                    list.add(matrix[i][l]);
                }
                if(++l > r) break;
            }
            return list.stream().mapToInt(Integer::intValue).toArray();
        }
    }

    class Solution2 {
        public boolean validateStackSequences(int[] pushed, int[] popped) {
            Deque<Integer> s = new LinkedList<>();
            int j = 0;
            for(int i = 0; i < pushed.length; ++i) {
                s.push(pushed[i]);
                while(!s.isEmpty() && s.peek() == popped[j]) {
                    s.pop();
                    j++;
                }
            }
            return s.isEmpty();
        }
    }

    class Solution3 {
        public int[] levelOrder(TreeNode root) {
            if(root == null) return new int[0];
            List<Integer> list = new LinkedList<>();
            Deque<TreeNode> q = new LinkedList<>();
            q.offer(root);
            while(!q.isEmpty()) {
                int size = q.size();
                for(int i = 0; i < size; ++i) {
                    TreeNode cur = q.poll();
                    list.add(cur.val);
                    if(cur.left != null) q.offer(cur.left);
                    if(cur.right != null) q.offer(cur.right);
                }
            }
            return list.stream().mapToInt(Integer::intValue).toArray();
        }
    }

    class Solution4 {
        List<List<Integer>> res = new LinkedList<>();
        public List<List<Integer>> levelOrder(TreeNode root) {
            preOrder(root, 0);
            return res;
        }
        private void preOrder(TreeNode root, int k) {
            if(root == null) return;
            if(res.size() <= k) res.add(new LinkedList<>());
            res.get(k).add(root.val);

            preOrder(root.left, k + 1);
            preOrder(root.right, k + 1);
        }
    }

    class Solution5 {
        List<List<Integer>> res = new LinkedList<>();
        public List<List<Integer>> levelOrder(TreeNode root) {
            preOrder(root, 0);
            return res;
        }

        private void preOrder(TreeNode root, int k) {
            if(root == null) return;
            if(res.size() <= k) res.add(new LinkedList<>());
            if(k % 2 == 0) res.get(k).add(root.val);
            else res.get(k).add(0, root.val);

            preOrder(root.left, k + 1);
            preOrder(root.right, k + 1);
        }
    }

    class Solution6 {
        public boolean verifyPostorder(int[] postorder) {
            return postOrder(postorder, 0, postorder.length-1);
        }
        private boolean postOrder(int[] pos, int l, int r) {
            if(l > r) return true;
            int m = l;
            while(pos[m] < pos[r]) m++;
            int p = m;
            while(pos[p] > pos[r]) p++;

            return p == r && postOrder(pos, l, m-1) && postOrder(pos, m, r-1);
        }
    }

    class Solution7 {
        List<List<Integer>> res = new LinkedList<>();
        public List<List<Integer>> pathSum(TreeNode root, int target) {
            dfs(root, target, new LinkedList<>());
            return res;
        }
        private void dfs(TreeNode root, int target, List<Integer> ret) {
            if(root == null) return;
            target -= root.val;
            if(root.left == null && root.right == null) {
                if(target == 0) {
                    ret.add(root.val);
                    res.add(new LinkedList<>(ret));
                    ret.remove(ret.size()-1);
                }
                return;
            }
            ret.add(root.val);
            dfs(root.left, target, ret);
            dfs(root.right, target, ret);
            ret.remove(ret.size()-1);
        }
    }

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    class Solution8 {
        public Node copyRandomList(Node head) {
            Map<Node, Node> map = new HashMap<>();
            Node cur = head;
            while(cur !=null ) {
                map.put(cur, new Node(cur.val));
                cur = cur.next;
            }
            for(Node x = head; x != null; x = x.next) {
                map.get(x).next = map.get(x.next);
                map.get(x).random = map.get(x.random);
            }
            return map.get(head);
        }
    }

    class Solution9 {
        public int[] getLeastNumbers(int[] arr, int k) {
            if(arr.length == 0 || k == 0) return new int[0];
            PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> (b-a));
            for(int i = 0; i < arr.length; ++i) {
                if(i < k) q.offer(arr[i]);
                else {
                    if(!q.isEmpty() && q.peek() > arr[i]) {
                        q.poll();
                        q.offer(arr[i]);
                    }
                }
            }
            return q.stream().mapToInt(Integer::intValue).toArray();
        }
    }

    class MedianFinder {
        PriorityQueue<Integer> l;
        PriorityQueue<Integer> r;

        /** initialize your data structure here. */
        public MedianFinder() {
            l = new PriorityQueue<>((a, b) -> (b-a));
            r = new PriorityQueue<>();
        }

        public void addNum(int num) {
            l.offer(num);
            r.offer(l.poll());
            if(l.size() + 1 < r.size()) {
                l.offer(r.poll());
            }
        }

        public double findMedian() {
            if(l.size() < r.size()) return r.peek();
            else return (double)(l.peek() + r.peek()) / 2;
        }
    }
}